home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / hzip.com / PNODE.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1991-01-08  |  4.6 KB  |  186 lines
  1. ////////////////////////////////////////////////////////////
  2. // Package node class implementation file
  3. // Copyright (c) 1991 by Azarona Software
  4. // All rights reserved. 
  5. ////////////////////////////////////////////////////////////
  6.  
  7. #include <stdlib.h>
  8. #include <stdio.h>
  9. #include <string.h>
  10. #include "pnode.h"
  11.  
  12. //
  13. // Methods for the pnode allocator
  14. //
  15.  
  16. pnode_allocator::pnode_allocator(int sz)
  17. // Allocate space for sz nodes
  18. {
  19.   data = new anode[size = sz];
  20.   if (data == 0) {
  21.      printf("No room to allocate pnode storage\n");
  22.      exit(1);
  23.   }
  24.  
  25.   data->node_cnt = 0; // Keeps track of number of nodes used
  26.   for (int i = 0; i<sz; i++) data[i].n = i+1; // Set up free list
  27.   data[sz-1].n = 0;
  28. }
  29.  
  30. void *pnode_allocator::alloc(void)
  31. // Grab a pnode from the free list
  32. {
  33.   unsigned i = data->n;    // Get free anode index
  34.   if (i == 0) return 0;    // No more room
  35.   data->node_cnt++;        // Keep track of used pnodes
  36.   data->n = (data + i)->n; // Move head of free list
  37.   return (void *)(data + i);
  38. }
  39.  
  40. void pnode_allocator::free(void *p)
  41. // Put p at the head of the free list
  42. {
  43.   ((anode *)p)->n = data->n;
  44.   data->n = (unsigned(p) - unsigned(data)) / sizeof(anode);
  45.   data->node_cnt--;
  46. }
  47.  
  48. //
  49. // Methods for the pnode class
  50. //
  51.  
  52. pnode *pnode::make_package(pnode *a, pnode *b)
  53. {
  54.   pnode *p;
  55.  
  56.   pnode *c = new pnode(a->wt + b->wt, 0, -1, 0);
  57.   if (c == 0) {
  58.      printf("No room for combined pnode\n");
  59.      exit(1);
  60.   }
  61.  
  62.   // Now, merge a and b pnodes into to this package
  63.  
  64.   if (a->n == 0) { // a is a singleton
  65.      c->n = a;
  66.      if (b->lvl == -1) { // b is internal
  67.         a->n = b->n;     // so skip it
  68.         delete b;        // and dump it
  69.      } else a->n = b;
  70.   }
  71.   else { // a is a package
  72.      if (b->n == 0) { // b is a singleton
  73.         c->n = b;
  74.         if (a->lvl == -1) { // a is internal
  75.            b->n = a->n;     // so skip it
  76.            delete a;        // and dump it
  77.         } else b->n = a;
  78.      }
  79.      else { // both a and b are packages
  80.         if (a->lvl == -1) { // a is internal
  81.            p = a->n;        // so skip it
  82.            delete a;        // and dump it
  83.         }                 
  84.         else p = a;           
  85.         c->n = p;
  86.         // find end a list
  87.         while(p->n) p = p->n; // p guaranteed to be non-null
  88.         if (b->lvl == -1) {   // b is internal
  89.            p->n = b->n;       // so skip it
  90.            delete b;          // and dump it
  91.         }
  92.         else p->n = b;        
  93.      }
  94.   }
  95.  
  96.   return c;
  97. }
  98.  
  99. void pnode::rmv_package(pnode *p)
  100. // Delete all nodes in the package p
  101. {
  102.   while(p) {
  103.     pnode *q = p->n;
  104.     delete p;
  105.     p = q;
  106.   }
  107. }
  108.  
  109.  
  110. pnode *nodeset::remove_front(void)
  111. {
  112.   pnode *p = data[0];
  113.   memmove(data, data+1, (cursor--)*sizeof(pnode *));
  114.   return p;
  115. }
  116.  
  117. //
  118. // Methods for the nodeset class
  119. //
  120.  
  121. void nodeset::package(void)
  122. // Packages up the nodeset in place
  123. {
  124.   int p = 0, q, nxtavl = 0;
  125.   while(p<cursor) { // Have at least one pnode
  126.     q = p+1;
  127.     if (q<cursor) { // Have at least two pnodes, so make package
  128.        data[nxtavl++] =
  129.           pnode::make_package(data[p], data[q]);
  130.        p += 2;
  131.     }
  132.     else {
  133.       // Singleton node, so toss complete package  
  134.       pnode::rmv_package(data[p]);
  135.       break;
  136.     }
  137.   }
  138.   cursor = nxtavl; // New size of nodeset
  139. }
  140.  
  141. void nodeset::setup_and_merge(nodeset &nset, long wts[], 
  142.                               unsigned char smap[], 
  143.                               int num_syms, int level)
  144. // ASSUMES LEVEL >= 0
  145. {
  146.   int p = num_syms - 1;
  147.   int q = 0;  // Start at head of nset
  148.   cursor = 0; // Start with an new empty nodeset
  149.  
  150.   while(1) {
  151.     if (p >= 0) {
  152.        if (q<nset.cursor) { // Dealing from both decks
  153.           if (wts[p] <= nset.data[q]->wt) {
  154.              pnode *baby = new pnode(wts[p], smap[p], level, 0);
  155.              if (baby == 0) {
  156.                 printf("No room for new pnode\n");
  157.                 exit(1);
  158.              }
  159.              data[cursor++] = baby;
  160.              p--;
  161.           }
  162.           else {
  163.             data[cursor++] = nset.data[q++];
  164.           }
  165.        }
  166.        else { // No more q left
  167.          for (; p >= 0; p--) {
  168.              pnode *baby = new pnode(wts[p], smap[p], level, 0);
  169.              if (baby == 0) {
  170.                 printf("No room for new pnode\n");
  171.                 exit(1);
  172.              }
  173.              data[cursor++] = baby;
  174.          }
  175.          break;
  176.        }
  177.     }
  178.     else { // No more p left, so copy rest of q;
  179.       int num_pnodes = nset.cursor - q;
  180.       memmove(data+cursor, nset.data+q, num_pnodes*sizeof(pnode *));
  181.       cursor += num_pnodes;
  182.       break;
  183.     }
  184.   }
  185. }
  186.